//import java.util.*;
//
//
//public class Solution {
//
//    private int[] dx = {-1, 0, 1, 0};
//    private int[] dy = {0, 1, 0, -1};
//
//    public static void main(String[] args) {
//        String[] strings = new String[]{"001001", "101001", "101101", "100101", "100101", "100101"};
//        int step = maze(strings);
//        System.out.println(step);
//
//    }
//
//    public static int maze(String[] inputs) {
//        if (inputs == null || inputs.length == 0) {
//            return 0;
//        }
//
//        int row = inputs.length;
//        int column = inputs[0].length();
//        char[][] maze = new char[inputs.length][inputs[0].length()];
//        for (int i = 0; i < inputs.length; i++) {
//            String rowData = inputs[i];
//            for (int j = 0; j < rowData.length(); j++) {
//                maze[i][j] = rowData.charAt(j);
//            }
//        }
//
//        Queue<String> common.queue = new common.list.LinkedList<String>();
//        Set<String> visited = new HashSet<>();
//        Map<String, Integer> stepMap = new HashMap<>();
//
//        String location = 0 + "-" + 0;
//        common.queue.add(location);
//        visited.add(location);
//        stepMap.put(location, 1);
//
//        while (!common.queue.isEmpty()) {
//            String currentLocation = common.queue.poll();
//            int step = stepMap.get(currentLocation);
//
//            int rowIndex = Integer.parseInt(currentLocation.split("-")[0]);
//            int columnIndex = Integer.parseInt(currentLocation.split("-")[1]);
//
//            int rowTmp = 0;
//            int columnTmp = 0;
//
//            // down
//            rowTmp = rowIndex + 1;
//            columnTmp = columnIndex;
//            String locationTmp = rowTmp + "-" + columnTmp;
//            if (valid(rowTmp, columnTmp, row, column) && !visited.contains(locationTmp)) {
//                if (maze[rowTmp][columnTmp] == '0') {
//                    if (rowTmp == row - 1) {
//                        return step + 1;
//                    }
//                    common.queue.add(locationTmp);
//                    visited.add(locationTmp);
//                    stepMap.put(locationTmp, step + 1);
//                }
//            }
//
//            // left
//            rowTmp = rowIndex;
//            columnTmp = columnIndex - 1;
//            locationTmp = rowTmp + "-" + columnTmp;
//            if (valid(rowTmp, columnTmp, row, column) && !visited.contains(locationTmp)) {
//                if (maze[rowTmp][columnTmp] == '0') {
//                    common.queue.add(locationTmp);
//                    visited.add(locationTmp);
//                    stepMap.put(locationTmp, step + 1);
//                }
//            }
//
//            //right
//            rowTmp = rowIndex;
//            columnTmp = columnIndex + 1;
//            locationTmp = rowTmp + "-" + columnTmp;
//            if (valid(rowTmp, columnTmp, row, column) && !visited.contains(locationTmp)) {
//                if (maze[rowTmp][columnTmp] == '0') {
//                    common.queue.add(locationTmp);
//                    visited.add(locationTmp);
//                    stepMap.put(locationTmp, step + 1);
//                }
//            }
//
//        }
//
//        return Integer.MAX_VALUE;
//    }
//
//    private static boolean valid(int rowIndex, int columnIndex, int row, int column) {
//        return rowIndex >= 0 && rowIndex < row && columnIndex >= 0 && columnIndex < column;
//    }
//
//
//    public void cleanRoom(Robot robot) {
//        HashSet<String> visited = new HashSet<>();
//        dfsClean(robot, visited, 0, 0, 0);
//    }
//
//    /**
//     *
//     * @param robot
//     * @param visited position has visited
//     * @param x start x
//     * @param y start y
//     * @param dir start dir
//     */
//    private void dfsClean(Robot robot, HashSet<String> visited, int x, int y, int dir) {
//        String pos = x + "-" + y;
//        robot.clean();
//        visited.add(pos);
//
//        for (int k = 0; k < 4; k++) {
//            int newDir = (dir + k) % 4;
//            int nx = x + dx[newDir];
//            int ny = y + dy[newDir];
//
//            String newpos = nx + "-" + ny;
//            if (!visited.contains(newpos) && robot.move()) {
//
//                dfsClean(robot, visited, nx, ny, newDir);
//
//                // back tracking
//
//                // 转一百八十度
//                robot.turnLeft();
//                robot.turnLeft();
//
//                // 向前走一格
//                robot.move();
//
//                // 把方向再恢复原状
//                robot.turnRight();
//                robot.turnRight();
//            }
//
//            robot.turnRight();
//        }
//    }
//
//}
